The present invention relates to comparison of geometric shapes and more particularly, the present invention relates to a way to measure how closely one representation of a segment matches another representation of the segment.
The need to compare geometric shapes arises in various applications relating to the use of data representations of geographic features. One such application is the measurement of geographic database accuracy. Other applications include vehicle positioning and road sign recognition.
One method for measuring shape accuracy involves measuring the unsigned area between a sampled segment and a ground truth segment. Referring to FIG. 1, a ground truth segment 10 is shown as a dashed line and a sampled segment 12 is shown as a solid line. Areas between the ground truth segment 10 and the sampled segment are indicated as A1, A2, and A3. According to this method, the larger the area between the segments, the greater is the deviation between the segments.
Another method for measuring shape accuracy is to measure the maximum deviation between a sampled segment and a ground truth segment. Referring to FIG. 2, a ground truth segment 20 is shown as a dashed line and a sampled segment 22 is shown as a solid line. Note that in order to obtain a true measure of a distance between the two segments, the segments should be aligned to minimize the area. However, this method does not specify how this alignment should be carried out.
There are at least two possible approaches for aligning a sampled segment and a ground truth segment so that the relative accuracy between them can be measured. FIG. 3 shows a first approach for aligning a sampled segment and a ground truth segment. According to this approach, the segments are first scaled so that the starting and ending nodes (i.e., endpoints) of the segments coincide. As shown graphically in FIG. 3, the segments are scaled so that the starting and ending nodes correspond to (0,0) and (1,0) respectively. Then, the unsigned area between the two segments is computed. This area is a measure of the relative accuracy between the two segments.
This approach has the disadvantage that it may not always yield an accurate measure of relative accuracy because aligning the segments as shown in FIG. 3 may not be the optimal alignment that yields the minimum area. For example, consider the ground truth segment 40 and the sampled segment 42, shown in FIG. 4. These two segments have a similar shape except at one of the endpoints. When they are aligned so that their starting and ending nodes correspond to (0,0) and (1,0) respectively, as described in the first approach, the alignment shown in FIG. 5 is obtained. As shown in FIG. 5, a relatively large area exists between the two segments. The segments 40 and 42 should be aligned as shown in FIG. 6 to yield a truer measure of relative accuracy.
A second approach for aligning a sampled segment and a ground truth segment is illustrated in FIGS. 7A, 7B and 7C. According to this approach, the features are first scaled so that the starting and ending nodes of each feature correspond to (0,0) and (1,0) respectively, as in the previous approach. Then, the unsigned area or deviation between the two segments is computed. Then, the sampled segment 42 is rotated through an incremental angle Δθ with respect to the ground truth segment 40 and the unsigned area or deviation between the two segments is computed again. The steps of rotating and computing are repeated successively until all values of −π≦θ≦π have been traversed, as indicated in FIGS. 7A, 7B, and 7C. The minimum area obtained using this approach is a measure of the relative accuracy between the two segments. The accuracy of this approach is a function of the angle increment Δθ. The smaller the angle increment, the greater is the accuracy of this approach. Although this approach yields an accurate measure of relative accuracy between a sampled segment and a ground truth segment, it is computationally intensive.
Accordingly, there exists a need for an improved way for aligning a pair of shapes in a manner which is computationally non-intensive and consistent for all segments.